package com.cyx;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author 陈裕星
 * @version 1.0
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 */
public class 括号生成之递归加剪枝 {
    static int n;
    static List<String> res = new ArrayList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        recursive("",0,0);

        System.out.println(res.toString());
    }

    /**
     *
     * @param str
     * @param left:左括号个数
     * @param right：右括号个数
     */
    static void recursive(String str,int left,int right){
        //推出条件
        if (left == n && right == n){
            res.add(str);
            return;
        }

        //剪枝
        if(right > left || left > n) return;

        //递归
        recursive(str + "(",left + 1,right);
        recursive(str + ")",left,right + 1);
    }
}
